
/*
 * Question: For a given binary tree, try to obtain a path
 * from the root to some leaf whose length is equal to the
 * hight of the tree minus one. If there are more than one
 * such pathes, the left most one is required.
 *
 * Date: 01/25/2012
 */

#include <iostream>
#include <stack>
#include "bitree.h"
using namespace std;

class bitree : public _bitree<bitree, char>
{
};

struct snode{
    bitree *rt;
    int tag;
};

/*
 * For general situations, it is necessary to calculate
 * the height of the specified binary tree first. Then,
 * the target path is obtained by travelling the tree.
 * Therefore, two travellings are needed to get the target
 * path. However, with the constrain that the length of
 * the target path is equal to the height of the tree minus
 * one, there is an optimization: in one travelling, the
 * target path is obtained. During the travelling, try to find
 * the height of the tree which is represented by the variable
 * 'max'. From left to right, every path will be checked.
 * When a longer path appears, the 'max' is updated by the
 * length of the path. Meaningwhile, if there is a path whose
 * length is 'max'-1, it must be previous 'max' path. So, the
 * previous 'max' path is save into 'tpath'. Otherwise, the
 * 'tpath' is cleared. For the new 'max' path, the target path
 * to its right will be found in following travelling.
 */
void path(bitree *rt)
{
    snode n;
    stack<snode> s, mpath, tpath, epath;
    int h = 0, max = 0;

    n.rt = rt; n.tag = 0;
    while (n.rt || !s.empty()){
        if (n.rt){
            s.push(n);
            h++;
            if (!n.rt->lchild && !n.rt->rchild){
                // cout << h << " "; // When arriving at a leaf, print the current path length.
                /*
                 * max: the maximum of the lengthes of current all pathes.
                 * mpath: the path whose length is 'max'.
                 * tpath: the target path.
                 * epath: a empty path, be used to clear 'tpath'.
                 */
                if (h > max){
                    if (max == h-1)
                        tpath = mpath;
                    else
                        tpath = epath;
                    max = h;
                    mpath = s;
                }
                else{
                    /*
                     * To the current 'max' path's right, if a 'max-1' path
                     * and its parallels have not appered, this path is the
                     * target path.
                     */
                    if (h == max-1 && tpath.empty())
                        tpath = s;
                }
            }
            n.rt = n.rt->lchild; n.tag = 0;
        }
        else{
            n = s.top(); s.pop();
            if (n.tag == 0){
                n.tag = 1;
                s.push(n);
                n.rt = n.rt->rchild; n.tag = 0;
            }
            else{
                n.rt = NULL;
                h--;
            }
        }
    }

    cout << endl;
    cout << "The length of the target path: " << tpath.size() << endl;
    cout << "The path is: ";
    while (!tpath.empty()){
        n = tpath.top(); tpath.pop();
        epath.push(n);
    }
    while (!epath.empty()){
        n = epath.top(); epath.pop();
        cout << n.rt->key << " ";
    }
    cout << endl;
}

int main()
{
    bitree *rt;

    bitree_create<bitree, char>(rt, "ex53.txt");
    path(rt);
    bitree_destory(rt);

    return 0;
}
